#include "pch/std_algorithm.h"
#include "pch/std_cmath.h"
#include "pch/std_set.h"
#include "pch/std_numbers.h"
#include "DelaunayTri.h"
#include "vector.h"

using namespace BaseGeo;

class Box {
private:
    Point left_down_point;
    Point right_up_point;

    void updateSize()
    {
        left = left_down_point.x;
        right = right_up_point.x;
        up = right_up_point.y;
        down = left_down_point.y;

        length = right - left;
        height = up - down;
    }
public:
    double left, right, up, down;
    double length, height;

    Box(const Point& left_down_point, const Point& right_up_point) :
        left_down_point(left_down_point), right_up_point(right_up_point)
    {
        updateSize();
    }

    void Reshape(const Vector& left_down_vector, const Vector& right_up_vector)
    {
        left_down_point += left_down_vector;
        right_up_point += right_up_vector;
        updateSize();
    }
};


static Box findBox(const std::vector<Point>& points)
{
    auto pair_for_x = std::minmax_element(points.begin(), points.end(), 
        [](const Point& point1, const Point& point2){ return point1.x < point2.x; }
    );
    auto pair_for_y = std::minmax_element(points.begin(), points.end(), 
        [](const Point& point1, const Point& point2){ return point1.y < point2.y; }
    );

    return Box(
        Point(pair_for_x.first->x, pair_for_y.first->y),
        Point(pair_for_x.second->x, pair_for_y.second->y)
    );
}


static Triangle buildSuperTriangle(const std::vector<Point>& points)
{
    const double expand_scale = 6.5;
    Box box = findBox(points);

    double edge_buff = box.length / expand_scale;
    Vector expand_v = Vector(1.0, 1.0) * edge_buff;
    box.Reshape(- expand_v, expand_v);

    double left_right_part = box.height / std::numbers::sqrt3;
    Point top = Point(
        box.length / 2, box.up + box.length * (std::numbers::sqrt3 / 2)
    );
    Point left = Point(
        box.left - left_right_part, box.down
    );
    Point right = Point(
        box.right + left_right_part, box.down
    );

    return Triangle(
        top, left, right
    );
}


void DelaunayTri::uniquePoints()
{
    std::sort(points.begin(), points.end());
    auto last = std::unique(points.begin(), points.end());
    points.erase(last, points.end());
}


DelaunayTri::DelaunayTri(const std::vector<Point>& points) : points(points) 
{
    uniquePoints();
}


class TriangleWithIndex : public Triangle {
public:
    std::set<uint32_t> index_set;
    TriangleWithIndex(const Triangle& triangle, const std::set<uint32_t>& index_set) :
        index_set(index_set), Triangle(triangle)
    {}

    Triangle GetTriangle() const
    {
        return Triangle(vertices[0], vertices[1], vertices[2]);
    }
};



static std::list<TriangleWithIndex> anticlockWiseBuildTriangles(const std::vector<Point>& point_list, const uint32_t insert_point_index, const std::set<uint32_t>& next_vertex_index_set)
{
    struct IndexWithTheta {
        uint32_t connected_to_index;
        double theta;

        IndexWithTheta(const uint32_t connected_to_index, const Vector& vector) :
            connected_to_index(connected_to_index), theta(vector.AngleWith(x_unit_vector))
        {
            if (vector.y < 0) {
                theta = 2 * std::numbers::pi - theta;
            }
        }

        bool operator<(const IndexWithTheta& other) const
        {
            return theta < other.theta;
        }
    };

    std::vector<IndexWithTheta> indices;
    std::list<TriangleWithIndex> triangle_list;
    uint32_t index_a, index_b;

    for (auto next_vertex_index : next_vertex_index_set) {
        indices.push_back(
            IndexWithTheta(
                next_vertex_index,
                Vector(point_list[insert_point_index], point_list[next_vertex_index])
            )
        );
    }
    std::sort(indices.begin(), indices.end());

    for (int i = 0; i < indices.size(); i++) {
        index_a = indices[i].connected_to_index;
        index_b = indices[(i + 1) % indices.size()].connected_to_index;

        triangle_list.push_back(
            TriangleWithIndex(
                Triangle(
                    point_list[index_a],
                    point_list[index_b],
                    point_list[insert_point_index]
                ),
                {index_a, index_b, insert_point_index}
            )
        );
    }

    return triangle_list;
}


template<typename key_type>
static std::vector<key_type> calSetsIntersection(const std::set<key_type>& set_x, const std::set<key_type>& set_y)
{
    std::vector<key_type> intersection = {};
    std::set_intersection(
        set_x.begin(), set_x.end(),
        set_y.begin(), set_y.end(),
        std::back_inserter(intersection)
    );

    return intersection;
}


static void removeTrianglesConnectToSuperTriangle(std::list<TriangleWithIndex>& triangle_list, const TriangleWithIndex& super_triangle)
{
    triangle_list.remove_if(
        [&super_triangle](TriangleWithIndex& triangle) {
            return calSetsIntersection(triangle.index_set, super_triangle.index_set).size() != 0;
        }
    );
}


std::list<Triangle> DelaunayTri::Triangulation()
{
    uint32_t point_num = points.size();
    TriangleWithIndex super_triangle = TriangleWithIndex(
        buildSuperTriangle(points),
        {point_num, point_num + 1, point_num + 2}
    );
    std::list<TriangleWithIndex> temp_triangle_list, temp_triangle_list_1;
    std::list<Triangle> out_triangle_list;
    std::vector<Point> points_in = points;  // Points list with super triangle vertices.
    std::set<uint32_t> next_vertex_index_set = {};

    temp_triangle_list.push_back(super_triangle);

    for (Point point : super_triangle.vertices) {
        points_in.push_back(point);
    }

    for (uint32_t i = 0; i < point_num; i++) {
        Point point = points_in[i];
        temp_triangle_list_1.clear();
        next_vertex_index_set.clear();

        for (TriangleWithIndex triangle_with_index : temp_triangle_list) {
            if (triangle_with_index.GetCircumCircle().IsPointInThis(point)) {
                next_vertex_index_set.merge(triangle_with_index.index_set);
            } else {
                temp_triangle_list_1.push_back(triangle_with_index);
            }
        }

        temp_triangle_list_1.splice(
            temp_triangle_list_1.end(),
            anticlockWiseBuildTriangles(points_in, i, next_vertex_index_set)
        );
        std::swap(temp_triangle_list, temp_triangle_list_1);
    }

    removeTrianglesConnectToSuperTriangle(temp_triangle_list, super_triangle);
    for (TriangleWithIndex triangle_with_index : temp_triangle_list) {
        out_triangle_list.push_back(triangle_with_index.GetTriangle());
    }

    return out_triangle_list;
}


const std::vector<Point>& DelaunayTri::GetPoints() const
{
    return points;
}
